package 剑指Offer.medium;

public class 二叉搜索树的后序遍历序列 {
    class Solution {
        public boolean verifyPostorder(int[] postorder) {
            return recursion(postorder, 0, postorder.length - 1);
        }

        private boolean recursion(int[] postorder, int i, int j) {
            if (i >= j) return true;
            int index = i;
            while (postorder[index] < postorder[j]) {
                index++;
            }
            //分割点为第一个大于根节点的位置，减1即为根结点的左子结点
            int splitPoint = index;
            //找到右子树右界并和根节点位置进行比对
            while (postorder[index] > postorder[j]) {
                index++;
            }
            return index == j && recursion(postorder, i, splitPoint - 1) && recursion(postorder, splitPoint, j - 1);
        }
    }
}
